package mht.practice.ListNode;

/**
 * Created by MHT on 2017/9/15.
 */
public class reGetKthNode {

    /**
     * 查找单链表中的倒数第K个结点（k > 0）
     * 最普遍的方法是，先统计单链表中结点的个数，然后再找到第（n-k）个结点。
     * 注意链表为空，k为0，k为1，k大于链表中节点个数时的情况
     * 时间复杂度为O（n）。代码略。 这里主要讲一下另一个思路，这种思路在其他题目中也会有应用。
     * 主要思路就是使用两个指针，先让前面的指针走到正向第k个结点
     * 这样前后两个指针的距离差是k-1，之后前后两个指针一起向前走，
     * 前面的指针走到最后一个结点时，后面指针所指结点就是倒数第k个结点
     */
    public static ListNode reGetKthNode(ListNode head, int k) {
        // 这里k的计数是从1开始，若k为0或链表为空返回null
        if (k == 0 || head == null) {
            return null;
        }

        ListNode q = head; // q在p前面  p--q
        ListNode p = head; // p在q后面

        // 让q领先p距离k
        while (k > 1 && q != null) {
            q = q.next;
            k--;
        }

        // 当节点数小于k，返回null
        if (k > 1 || q == null) {
            return null;
        }

        // 前后两个指针一起走，直到前面的指针指向最后一个节点
        while (q.next != null) {
            p = p.next;
            q = q.next;
        }

        // 当前面的指针指向最后一个节点时，后面的指针指向倒数k个节点
        return p;
    }


    /**
     * 递归打印出倒数第k位的值
     * @param head
     * @param dist
     */
    static int level = 0;
    public static void reGetKthNodeRec(ListNode head, int k) {

        if(head == null){
            return;
        }
        if(k == 1){
            return;
        }

        reGetKthNodeRec(head.next, k);
        level++;
        if(level == k) {
            System.out.println(head.val);
        }
    }
}
